home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / pdsrt211.arc / MERGE.C < prev    next >
Text File  |  1990-06-18  |  4KB  |  152 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <alloc.h>
  5. #include <limits.h>
  6.  
  7. #include "queue.h"
  8.  
  9. typedef struct RunStruct {
  10.     unsigned long   Begin;
  11.     unsigned long   Count;
  12.     }               RUN_ENT;
  13.  
  14. static struct RunArray {
  15.     unsigned long   Current;
  16.     unsigned long   Count;
  17.     int             Index;
  18.     char          **Buf;
  19.     }              *RA;
  20.  
  21. static unsigned long BufSize;
  22. static unsigned BufCount;
  23. static char   **OutBuf;
  24. static int      O_Index;
  25. static int      Low;
  26.  
  27. void            FillRunBuffer (int x);
  28. void            WriteOutputBuffer (void);
  29.  
  30.  void
  31. Merge (void) {
  32.     extern FILE    *fint, *fout;
  33.     extern QUE_DEF  Runs;
  34.     extern int      RecLen;
  35.     extern int      comp(const void *a, const void *b);
  36.     extern char   **SortArray;
  37.     extern int      S_ArraySize;
  38.     extern char     IntName[65];
  39.  
  40.     int             i, j;
  41.     QUE_ENTRY      *t;
  42.     RUN_ENT        *p;
  43.     unsigned long   MemLeft;
  44.  
  45.     for (i = 0; i < S_ArraySize; ++i) free(SortArray[i]);
  46.     free(SortArray);
  47.     MemLeft = (S_ArraySize * sizeof(char far *)) + (S_ArraySize * (RecLen + 2));
  48.  
  49.     if ((fint = freopen(IntName, "r", fint)) == NULL) {
  50.         fprintf(stderr, "%s\n", IntName);
  51.         fprintf(stderr, "Major error! %d", errno);
  52.         perror("");
  53.         exit(1);
  54.         }
  55.  
  56.     if ( (RA = malloc(Runs.Count * sizeof(struct RunArray) ) ) == NULL) {
  57.         fprintf(stderr, "Major Error. Insufficient memory for run array.\n");
  58.         exit(1);
  59.         }
  60.     MemLeft -= (Runs.Count * sizeof(struct RunArray));
  61.  
  62.     BufSize = MemLeft / (Runs.Count + 1);
  63.     if (BufSize > UINT_MAX) BufSize = UINT_MAX;
  64.     BufCount = (int) (BufSize / (RecLen + 2 + sizeof(char *)));
  65.     BufSize = BufCount * (RecLen + 2);
  66.  
  67.     for (i = 0, t = Runs.Head; t != NULL; ++i, t = t->Next) {
  68.         p = t->Body;
  69.         RA[i].Current = p->Begin;
  70.         RA[i].Count = p->Count;
  71.         RA[i].Index = 0;
  72.         if ((RA[i].Buf = malloc(BufCount * sizeof(char *))) == NULL) {
  73.             fprintf(stderr, "Major Error. Insufficient memory for run item\n");
  74.             exit(1);
  75.             }
  76.         MemLeft -= BufCount * sizeof(char *);
  77.         for (j = 0; j < BufCount; ++j) {
  78.             if ((RA[i].Buf[j] = malloc(RecLen + 2)) == NULL) {
  79.                 fprintf(stderr, "Major Error. Insufficient memory for run item buffer.\n");
  80.                 exit(1);
  81.                 }
  82.             MemLeft -= RecLen + 2;
  83.             }
  84.         }
  85.  
  86.     if ((OutBuf = malloc(BufCount * sizeof(char *))) == NULL) {
  87.         fprintf(stderr, "Insufficient memory: 3\n");
  88.         exit(1);
  89.         }
  90.     MemLeft -= BufCount * sizeof(char *);
  91.     for (j = 0; j < BufCount; ++j) {
  92.         if ((OutBuf[j] = malloc(RecLen + 2)) == NULL) {
  93.             fprintf(stderr, "Insufficient memory: 4\n");
  94.             exit(1);
  95.             }
  96.         MemLeft -= RecLen + 2;
  97.         }
  98.     O_Index = 0;
  99.  
  100.     for (i = 0; i < Runs.Count; ++i) FillRunBuffer(i);
  101.  
  102.     Low = 0;
  103.  
  104.     while (1) {
  105.         for (Low = 0, i = 1; i < Runs.Count; ++i) {
  106.             if (comp(&RA[i].Buf[RA[i].Index], &RA[Low].Buf[RA[Low].Index]) < 0)
  107.                 Low = i;
  108.             }
  109.         if (RA[Low].Buf[RA[Low].Index] == NULL) break;
  110.         strcpy(OutBuf[O_Index++], RA[Low].Buf[RA[Low].Index++]);
  111.         if (RA[Low].Index >= BufCount) FillRunBuffer(Low);
  112.         if (O_Index >= BufCount) WriteOutputBuffer();
  113.         }
  114.  
  115.     if (O_Index > 0) WriteOutputBuffer();
  116.     fclose(fint);
  117.     fclose(fout);
  118.     }
  119.  
  120.  
  121.  
  122.  void
  123. FillRunBuffer (int x) {
  124.     int             i;
  125.  
  126.     fseek(fint, RA[x].Current, SEEK_SET);
  127.     for (i = 0; (i < BufCount) && (i < RA[x].Count); ++i)
  128.         fgets(RA[x].Buf[i], RecLen, fint);
  129.     RA[x].Count -= i;
  130.     for (; i < BufCount; ++i) RA[x].Buf[i] = NULL;
  131.     RA[x].Current = ftell(fint);
  132.     RA[x].Index = 0;
  133.     }
  134.  
  135.  
  136.  void
  137. WriteOutputBuffer (void) {
  138.     extern int      errno;
  139.     extern long     OutCount;
  140.     int             i;
  141.  
  142.     for (i = 0; i < O_Index; ++i) {
  143.         fputs(OutBuf[i], fout);
  144.         if (errno) {
  145.             perror("I/O error on output file");
  146.             exit(1);
  147.             }
  148.         OutCount++;
  149.         }
  150.     O_Index = 0;
  151.     }
  152.